If the sides are 10^5, Dijkstra can use it.
When the vertex is 10^5, the edge is 10^10 in general, but if there is an additional constraint that the edge is 10^5, then Dijkstra method O((E+V)log V) can be used ---
This page is auto-translated from /nishio/辺が10^5ならダイクストラ使える. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.